/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-25
 * Time: 16:05
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution3 {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return ;
        // 1:找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 逆序准备工作：新的头结点
        ListNode head1 = head;
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;// 将上半段尾插null，分开标志

        // 2：逆序头插(很明显头插一直要用到的指针是头结点，这是关键)，这里逆序链表头结点是虚拟节点注意注意！！！！
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = cur.next;
        }

        // 3:合并两个链表(尾插)双指针
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        ListNode cur1 = head1, cur2 = head2.next;
        while (cur1.next != null) {// 左半链表长度>=右半
            // 先插左
            prev.next = cur1;
            cur1 = cur1.next;
            prev = prev.next;
            //  在插右
            if (cur2.next != null) {
                prev.next = cur2;
                cur2 = cur2.next;
                prev = prev.next;
            }
        }

    }
}
public class Test3 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        solution3.reorderList(node1);

    }
}
